package sort.onlogn.my_quick_sort_test;

import java.util.Arrays;
import java.util.Random;

/**
 * @author yeyangtao created at 2021/3/2 20:48
 */
public class QuickSort20210302 {
    public static void main(String[] args) {
        int[] a = new Random().ints(0, 100)
                .limit(10)
                .toArray();
        System.out.println(Arrays.toString(a));
        quickSort(0, a.length - 1, a);
        System.out.println(Arrays.toString(a));
    }

    private static void quickSort(int left, int right, int[] a) {
        if (left >= right) {
            return;
        }
        int p = partition(left, right, a);
        quickSort(left, p - 1, a);
        quickSort(p + 1, right, a);
    }

    private static int partition(int left, int right, int[] a) {
        int i = left;
        int flag = a[right];
        for (int j = left; j <= right; j++) {
            if (a[j] < flag) {
                if (i != j) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
                i++;
            }
        }
        int temp = a[i];
        a[i] = a[right];
        a[right] = temp;
        return i;
    }
}
